/*
 *name:zhang-lingfan
 *e-mail:1797098277@qq.com
 *qq:1797098277
 *
 *
 *程序说明：实现calculator,即计算器功能。
 *
 *
 */
#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include<queue>
#include<map>
#include <math.h>

using namespace std;

class node
{
public:
	double num;
	char op;
	bool flag;//true 数字，false 字符
	node()
	{
		num = 0;
		op = '#';
		flag = 0;
	}//初始化
};

int Convert(string s);//转换为后缀表达式
string choose(string s);//筛选字符


int main()
{
	string s1 = choose("1.23sf4g6");
	string s2 = choose("1.2sdf3!!3-0.23");
	string s3 = choose("1t.y21*(3RR−4T + 1s.s00) ");//测试括号的功能
	string s4 = choose("1((2");//测试括号匹配
	string s5 = choose("1)(2");//测试括号匹配
	string s6 = choose("1()+2");//测试空括号不影响表达式的计算
	string s7 = choose("(1+2)");
	string s8 = choose("1.22.3");//测试小数点非法情况

	Convert(s1);
	Convert(s2);
	Convert(s3);
	Convert(s4);
	Convert(s5);
	Convert(s6);
	Convert(s7);
	Convert(s8);

	system("pause");
	return 0;

};
unsigned int c_in_str(const char * str, char ch)//   统计字符
{
	unsigned int count = 0;

	while (*str)  //字符串本身自己带有空值字符
	{
		if (*str == ch)
			count++;
		str++;
	}
	return count;
}


string choose(string s)//筛选字符
{
	//step 1，去掉不是数字和运算符的字符，得到数组l
	int len = s.length();
	char l[30] = { 0 };
	int c = 0;
	for (int i = 0; i < s.size(); i++)
	{
		char b = s[i];
		int a = int(b);
		//cout << a << endl;
		if (a < 58 && a>39 && a != 44) {
			l[c] = s[i];
			c++;
			//cout << l << endl;
			continue;
		}
		else {
			if (a < 30 && a>27) {
				l[c] = s[i];
				c++;
				//cout << l << endl;
				continue;
			}
			else { continue; }

		}
	}
///排除括号非法的情况
	//情形1：排除左右括号不匹配的情况
	unsigned int a1 = c_in_str(l, ')');
	unsigned int a2 = c_in_str(l, '(');
	//unsigned int a3= c_in_str(l, '.');
	//cout << a1 << endl << a2 << endl;
	if (a1 != a2)
		return "\'括号不匹配的表达式\'";
	//情形2：排除右括号在左括号前面的情况
	int pos1 = s.find('(');
	int pos2 = s.find(')');
	//cout << pos1 << endl << pos2 << endl;
	if (pos1 > pos2)
		return "\'括号不匹配的表达式\'";

	return l;
};

int Convert(string s) {
	cout<< "原表达式  " << s << "  的后缀表达式为：  ";
	//
	if (s == "\'括号不匹配的表达式\'")//根据筛选字符的结果，若括号不匹配则输出“Error！”并结束
	{
		cout << "Error!" << endl << endl;
		return 0;
	}
	map<char, int> m;
	m['+'] = m['-'] = 1;
	m['*'] = m['/'] = 2;


	string s1 = s;
	queue<node> q;//存放后缀表达式
	stack<char> op;//临时存放操作符

	

	for (int i = 0; i < s1.length();)
	{
		//cout << "s1[i]: " << s1[i] << endl;
		node temp;
		//step one ， 存放数字
		if (s1[i] >= '0'&& s1[i] <= '9') {
			temp.num = s1[i++] - '0';
			temp.flag = true;

			if (s1[i] >= '0' && s1[i] <= '9')
			{
				while (i < s1.length() && s1[i] >= '0' && s1[i] <= '9') {
					temp.num = temp.num * 10 + (s1[i] - '0');
					i++;
				}
			}
			else if (s[1] == '.')
			{
				int c = i;
				i++;
				
				while ((i < s1.length() && s1[i] >= '0' && s1[i] <= '9')|| (i < s1.length() && s1[i] == '.'))
				{
					if (s1[i] >= '0' && s1[i] <= '9')
					{
						double k = pow(10, -(i - c));
						temp.num = temp.num + (s1[i] - '0')*k;
						i++;
					}
					else if (s1[i] == '.')
						//排除小数点非法的情况
					{
						cout << "Error!" << endl << endl;
						return 0;
					}
					else if (s1[i] != '.' && s1[i]<'0' && s1[i]>'9')
					{
						break;
					}
					
				}

			}
		

			q.push(temp);
			cout << temp.num << " ";
		}

		//step two , 存放运算符
		else {
			//step two-1
			if (op.empty() || s1[i] == '(') {
				op.push(s1[i]);
			}
			else if (s1[i] == ')') {
				while (op.top() != '(') {
					temp.op = op.top();
					temp.flag = false;
					q.push(temp);
					cout << op.top() << " ";
					op.pop();


				}
				op.pop();
			}
			//
			else if (m[s1[i]] > m[op.top()]) {
				//弹出>=当前op
				op.push(s1[i]);

			}
			//
			else if (m[s1[i]] <= m[op.top()]) {
				while (!op.empty() && m[s1[i]] <= m[op.top()] && op.top() != '(') {
					temp.op = op.top();
					temp.flag = false;
					q.push(temp);
					cout << op.top() << " ";
					op.pop();

				}
				op.push(s1[i]);
			}
			i++;
		}
	}
	int op_size = op.size();

	for (int i = 0; i < op_size; i++) {
		cout << op.top() << " ";
		node temp;
		temp.op = op.top();
		temp.flag = false;
		q.push(temp);
		op.pop();
	}
	cout << endl;

	int q_size = q.size();
	stack<double> num;//存放数字
	for (int i = 0; i < q_size; i++) {
		if (q.front().flag == true) {
			num.push(q.front().num);
			q.pop();
		}
		else {
			double t1, t2;
			t2 = num.top();
			num.pop();
			t1 = num.top();
			num.pop();

			if (q.front().op == '+') num.push(t1 + t2);
			else if (q.front().op == '-') num.push(t1 - t2);
			else if (q.front().op == '*') num.push(t1 * t2);
			else if (q.front().op == '/') num.push(t1 / t2);

			q.pop();

		}
	}
	cout << "原表达式  " << choose(s1) << "  的计算结果为 : " << num.top() << endl<<endl;

	return 0;
}
